package stmo.树.二叉树;

import stmo.队列.Queue;

public class TreeTest10 <Key extends Comparable<Key>,Value>{

    private Node root;

    private int N;

    public class Node {
        private Key key;
        private Value value;
        private Node left;
        private Node right;

        public Node(Key key,Value value,Node left,Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public int size() {
        return N;
    }

    public void put(Key key,Value value) {
        root = put(root,key,value);
    }

    public Node put(Node x,Key key,Value value) {
            if (x == null) {
                N++;
                return new Node(key,value,null,null);
            }
            int i = key.compareTo(x.key);
            if (i < 0) {
                x.left = put(x.left, key, value);
            }else if (i > 0) {
                x.right = put(x.right, key, value);
            }else {
                x.value = value;
            }
            return x;
    }

    public Value get(Key key) {
        return get(root, key);
    }

    public Value get(Node x,Key key) {
        if (x == null) {
            return null;
        }
        int i = key.compareTo(x.key);
        if (i < 0) {
            return get(x.left,key);
        }else if (i > 0) {
            return get(x.right,key);
        }else  {
            return x.value;
        }
    }

    public void delete(Key key) {
        delete(root,key);
    }

    public Node delete(Node x,Key key) {
        if (x == null) {
            return null;
        }
        int i = key.compareTo(x.key);
        if (i < 0) {
            x.left = delete(x.left, key);
        }else if (i > 0) {
            x.right = delete(x.right,key);
        }else {
            N--;
            if (x.right == null) {
                return x.left;
            }
            if (x.left == null) {
                return x.right;
            }
            Node minNode = x.right;
            while (x.left != null) {
                minNode = minNode.left;
            }
            Node n = x.right;
            while (n.left != null) {
                if (n.left.left == null) {
                    n.left = null;
                }else {
                    n = n.left;
                }
            }
            minNode.left = x.left;
            minNode.right = x.right;
            x = minNode;
        }
        return x;
    }

    public Key min() {
        return min(root).key;
    }

    public Node min(Node x) {
        if (x.left != null) {
            return min(x.left);
        }else {
            return x;
        }
    }

    public Key max() {
        return min(root).key;
    }

    public Node max(Node x) {
        if (x.right != null) {
            return max(x.right);
        }else {
            return x;
        }
    }

    public Queue<Key> qian() {
        Queue<Key> keys = new Queue<>();
        qian(root,keys);
        return keys;
    }

    public void qian(Node x,Queue<Key> keys) {
        if (x == null) {
            return;
        }
        keys.enqueue(x.key);
        if (x.left != null) {
            qian(x.left,keys);
        }
        if (x.right != null) {
            qian(x.right,keys);
        }
    }

}
